# -*- coding:utf-8 -*-

"""采用双向循环链表
"""

# overload 只是类型检查，并不能重载函数
from linked import Linked


class josephus_array:

    def __init__(self, n:int, m:int, k=1):
        self.alives = list(range(1, n + 1))
        self.kills = list()

        self.n = n
        self.m = m 
        self.k = k

    def stay_alive(self):

        i = 0
        pos = 0
        while len(self.alives) > self.k:
            pos += 1
            print(pos)
            if pos in self.alives:
                i += 1
            if i % self.m == 0 and i > 0:
                self.alives.remove(pos)
                self.kills.append(pos)
                i = 0
            # 构造一个循环列表
            if pos >= self.n: 
                pos %= self.n 


def josephus_linked(n, m, k=1):

    # 初始化双向循环链表
    link = Linked()
    kill_link = Linked()
    # for d in range(1, n + 1):
    #     link.append(d)

    link.append([i for i in range(1, n + 1)])
    print(link.datas())

    target_node = link.link
    i = 0
    while link.size > k:

        i += 1
        if i == m:
            link.remove(target_node.data)
            kill_link.append(target_node.data)
            i = 0
        target_node = target_node.next
    return link, kill_link


def recursice(n, m, d=None):
    """
    :param n 序列总数
    :param m 出列数
    :param d 死亡序号
    """
    if d is None:
        d = n
    
    if(d == 1):
        return (m -1) % n
    else:
        return (recursice(n-1, m, d-1) + m) % n

if __name__ == "__main__":
    
    # print("->%d"%(recursice(41,3)+1))
    
    # i = 1
    # while i <= 41:
    #     print(recursice(41, 3, i) + 1)
    #     i += 1

    # print(recursice(41, 3, 41) + 1)

    # ja = josephus_array(41, 3, 2)
    # ja.stay_alive()
    # print(ja.alives)
    # print(ja.kills)

    result = josephus_linked(41, 3)
    print(result[0].datas())
    print(result[1].datas())
